package com.wrial.kind.design;
/*
 * @Author  Wrial
 * @Date Created in 23:33 2020/8/14
 * 合并区间
 

 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MergeRagion {

    /**
     * 1.对intervals根据intervals[0]的值进行排序
     * 2.使用一个int[] curAns 存当前满足条件的区间
     * 3.if 下一个的左边大于上一个的右边，那就说明没有交集，将curAns加入ans，并更新curAns
     * 4.if 下一个的左边小于等于上一个的右边，那就说明有交集，将curAns[1]更新为max(interval[i-1][1],intervals[i],[1])
     * 5.将最后一个curAns加入，然后吧ans转换为返回类型
     */
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) return intervals;
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        int[] curAns = intervals[0];  //表示一个连续区间
        List<int[]> ans = new ArrayList<>();
        for (int i = 1; i < intervals.length; i++) {
            // 不重合
            if (intervals[i][0] > curAns[1]) {
                ans.add(curAns);
                curAns = intervals[i];
            } else {
                curAns[1] = Math.max(curAns[1], intervals[i][1]);
            }
        }
        //最后一定会剩下一个
        ans.add(curAns);
        int[][] ret = new int[ans.size()][2];
        for (int i = 0; i < ans.size(); i++) {
            System.arraycopy(ans.get(i), 0, ret[i], 0, 2);
        }
        return ret;
    }

}
